package com.lfg.leetcode.leetcode500;


import com.alibaba.fastjson.JSON;

public class No912SortArray {
    public static void main(String[] args) {
        int[] ret2 = sortArray(new int[]{5, 1, 1, 2, 0, 0});
        System.out.println(JSON.toJSONString(ret2));
    }

    public static int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }


    public static void quickSort(int[] nums, int start, int end) {
        int i=start;
        int j=end;
        if (i >= j) {
            return;
        }
        int mid = (i + j) / 2;

        while (i < j) {
            while (i < mid && nums[i] <= nums[mid]) {
                i++;
            }
            if (i < mid) {
                swap(nums, i, mid);
                mid = i;
            }
            while (j > mid && nums[j] >= nums[mid]) {
                j--;
            }
            if (j > mid) {
                swap(nums, j, mid);
                mid = j;
            }
            if (i == j) {
                break;
            }

        }

        quickSort(nums, start, mid - 1);
        quickSort(nums, mid + 1, end);
    }

    public static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}



